{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Length of Semi-Decreasing Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubarrayLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长半递减数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code>。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 的&nbsp;<em><strong>最长半递减子数组&nbsp;</strong></em>的长度，如果没有这样的子数组则返回 <code>0</code>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>子数组</strong> 是数组内的连续非空元素序列。</li>\n",
    "\t<li>一个非空数组是 <strong>半递减</strong> 的，如果它的第一个元素 <strong>严格大于</strong> 它的最后一个元素。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> nums = [7,6,5,4,3,2,1,6,10,11]\n",
    "<b>输出：</b> 8\n",
    "<b>解释：</b> 取子数组 [7,6,5,4,3,2,1,6]。\n",
    "第一个元素是 7，最后一个元素是 6，因此满足条件。\n",
    "因此，答案是子数组的长度，即 8。\n",
    "可以证明，在给定条件下，没有长度大于 8 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b> nums = [57,55,50,60,61,58,63,59,64,60,63]\n",
    "<b>输出：</b> 6\n",
    "<b>解释：</b> 取子数组 [61,58,63,59,64,60].\n",
    "第一个元素是 61，最后一个元素是 60，因此满足条件。\n",
    "因此，答案是子数组的长度，即 6。\n",
    "可以证明，在给定条件下，没有长度大于 6 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 3:</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b> nums = [1,2,3,4]\n",
    "<b>输出：</b> 0\n",
    "<b>解释：</b> 由于给定数组中没有半递减子数组，答案为 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-length-of-semi-decreasing-subarrays](https://leetcode.cn/problems/maximum-length-of-semi-decreasing-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-length-of-semi-decreasing-subarrays](https://leetcode.cn/problems/maximum-length-of-semi-decreasing-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,6,5,4,3,2,1,6,10,11]', '[57,55,50,60,61,58,63,59,64,60,63]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        # if nums == [-987,-255,-657,-81,-733,980]: return 3\n",
    "        cands = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            cands[num].append(i)\n",
    "        \n",
    "        \n",
    "        min_idx = float('inf')\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        for k in sorted(cands, reverse=True):\n",
    "            ans = max(ans, cands[k][-1] - min_idx + 1)\n",
    "            min_idx = min(min_idx, cands[k][0])\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        [6,0,8,2,1,5]\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        st = []\n",
    "        for k, v in enumerate(nums):\n",
    "            if len(st) == 0:\n",
    "                st.append((k, v))\n",
    "            else:\n",
    "                if v > st[-1][1]:\n",
    "                    st.append((k, v))\n",
    "        ok = 0\n",
    "        if len(st) == 0:\n",
    "            return len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            idx = len(nums) - 1 - i\n",
    "            if len(st) == 0:\n",
    "                break\n",
    "            while len(st) > 0 and st[-1][1] > nums[idx]:\n",
    "                ok = max(ok, idx - st[-1][0] + 1)\n",
    "                st.pop()\n",
    "        return ok\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maxSubarrayLength([7, 6, 5, 4, 3, 2, 1, 6, 10, 11]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            pstart = i\n",
    "            pend = len(nums) - 1\n",
    "            while pstart < pend:\n",
    "                if nums[pstart] > nums[pend]:\n",
    "                    length = pend - pstart + 1\n",
    "                    if length > res:\n",
    "                        res = length\n",
    "                    break\n",
    "                else:\n",
    "                    pend -= 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        result, stack, i, n = 0, [], 0, len(nums)\n",
    "        while i < n:\n",
    "            (not stack or nums[stack[-1]] < nums[i]) and stack.append(i)\n",
    "            i += 1\n",
    "        while result < i:\n",
    "            i -= 1\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                result = max(result, i - stack.pop() + 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r = 0\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j > i and nums[j] >= nums[i]:\n",
    "                j -= 1\n",
    "            if j > i:\n",
    "                r = max(r, j - i + 1)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        max_length = 0\n",
    "        stack = [[nums[0], 0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < stack[0][0]:\n",
    "                max_length = i + 1\n",
    "            elif nums[i] > stack[-1][0]:\n",
    "                stack.append([nums[i], i])\n",
    "            else:\n",
    "                left = 0\n",
    "                right = len(stack) - 1\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if stack[mid][0] > nums[i]:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                if stack[left][0] > nums[i]:\n",
    "                    max_length = max(max_length, i - stack[left][1] + 1)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        a = [0]\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            idx = bisect.bisect_right(a, nums[i], key = lambda x: nums[x])\n",
    "            if idx != len(a):\n",
    "                ans = max(ans, i - a[idx] + 1)\n",
    "            if nums[i] > nums[a[-1]]:\n",
    "                a.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        stack = [] # up\n",
    "        ans = 0\n",
    "        for k, v in enumerate(nums):\n",
    "            pos = bisect_right(stack, [v, k])\n",
    "            if pos != len(stack):\n",
    "                ans = max(ans, k - stack[pos][1] + 1)\n",
    "            else:\n",
    "                stack.append([v, k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        que = [[nums[0],0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>que[-1][0]:\n",
    "                que.append([nums[i],i])\n",
    "            elif nums[i]==que[-1][0]:\n",
    "                continue\n",
    "            else:\n",
    "                ii = bisect.bisect_left(que,[nums[i],math.inf])\n",
    "                res = max(res,i-que[ii][1]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        st, res = [], 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if not st or nums[st[-1]] < num:\n",
    "                st.append(i)\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            while st and nums[st[-1]] > nums[i]:\n",
    "                res = max(res, i - st.pop() + 1)\n",
    "            if res >= i:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [nums[0]]\n",
    "        que = dict()\n",
    "        que[nums[0]] = 0\n",
    "        ans = 0\n",
    "        for i, j in enumerate(nums):\n",
    "            if j > s[-1]:\n",
    "                que[j] = i \n",
    "                s.append(j)\n",
    "            elif j == s[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                idx = que[s[bisect_right(s, j)]]\n",
    "                if i - idx + 1 > ans:\n",
    "                    ans = i - idx + 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        # 单调栈里数字单调递增\n",
    "        stack = []\n",
    "\n",
    "        ans = 0\n",
    "        for idx, ii in enumerate(nums):\n",
    "            left = 0\n",
    "            right = len(stack) - 1\n",
    "\n",
    "            # 找到单调栈里最小的比当前数字大的数字\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[stack[mid]] <= ii:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            \n",
    "            # 有更大的数字，可以更新答案\n",
    "            if stack and nums[stack[left]] > ii:\n",
    "                ans = max(ans, idx - stack[left] + 1)\n",
    "            \n",
    "            # 如果栈为空（初始）或当前数字比单调栈最大的数字更大，进入单调栈\n",
    "            # （不违反单调栈“单调递增”限制的情况下就能进入）\n",
    "            if not stack or (stack and ii > nums[stack[-1]]):\n",
    "                stack.append(idx)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "  def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "\n",
    "      st = []\n",
    "      for k, v in enumerate(nums):\n",
    "          if len(st) == 0:\n",
    "              st.append((k, v))\n",
    "          else:\n",
    "              if v > st[-1][1]:\n",
    "                  st.append((k, v))\n",
    "      ok = 0\n",
    "      if len(st) == 0:\n",
    "          return len(nums)\n",
    "      for i in range(len(nums)):\n",
    "          idx = len(nums) - 1 - i\n",
    "          if len(st) == 0:\n",
    "              break\n",
    "          while len(st) > 0 and st[-1][1] > nums[idx]:\n",
    "              ok = max(ok, idx - st[-1][0] + 1)\n",
    "              st.pop()\n",
    "      return ok\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maxSubarrayLength([7, 6, 5, 4, 3, 2, 1, 6, 10, 11]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        stack = [] # [index, val]\n",
    "        ans = 0\n",
    "        for i,v in enumerate(nums):\n",
    "\n",
    "            l = 0\n",
    "            r = len(stack) - 1\n",
    "            while l < r:\n",
    "                mid = l + (r-l)//2\n",
    "\n",
    "                if stack[mid][1] > v:\n",
    "                    r = mid\n",
    "                elif stack[mid][1] < v:\n",
    "                    l = mid + 1\n",
    "                elif stack[mid][1] == v:\n",
    "                    l = mid + 1\n",
    "            \n",
    "            if stack and stack[l][1] > v:\n",
    "                # print(l, stack[l][0],stack[l][1], i,v)\n",
    "                ans = max(ans, i - stack[l][0] + 1)\n",
    "\n",
    "            # add to stack if empty or it is monotonic increasing\n",
    "            if not stack or stack[-1][1] < v:\n",
    "                stack.append([i,v])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        temp=sorted(list(set(nums+[-inf])))\n",
    "        ntemp=len(temp)\n",
    "        tree=[-inf]*(ntemp+1)\n",
    "        n=len(nums)\n",
    "        def update(x,value):\n",
    "            while x<=ntemp:\n",
    "                tree[x]=max(value,tree[x])\n",
    "                x+=x&(-x)\n",
    "            return \n",
    "        def query(x):\n",
    "            res=-inf\n",
    "            while x>0:\n",
    "                res=max(res,tree[x])\n",
    "                x-=x&(-x)\n",
    "            return res\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            b=bisect_left(temp,nums[i])\n",
    "            j=query(b)\n",
    "            ans=max(ans,j-i+1)\n",
    "            update(b+1,i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        temp=sorted(list(set(nums+[-10000000000])))\n",
    "        ntemp=len(temp)\n",
    "        tree=[-inf]*(ntemp+1)\n",
    "        n=len(nums)\n",
    "        def update(x,value):\n",
    "            while x<=ntemp:\n",
    "                tree[x]=max(value,tree[x])\n",
    "                x+=x&(-x)\n",
    "            return \n",
    "        def query(x):\n",
    "            res=0\n",
    "            while x>0:\n",
    "                res=max(res,tree[x])\n",
    "                x-=x&(-x)\n",
    "            return res\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            b=bisect_left(temp,nums[i])\n",
    "            j=query(b)\n",
    "            ans=max(ans,j-i+1)\n",
    "            x=bisect_left(temp,nums[i])+1\n",
    "            update(x,i)\n",
    "        return ans if ans>1 else 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        temp=sorted(list(set(nums+[-inf])))\n",
    "        ntemp=len(temp)\n",
    "        tree=[-inf]*(ntemp+1)\n",
    "        n=len(nums)\n",
    "        def update(x,value):\n",
    "            while x<=ntemp:\n",
    "                tree[x]=max(value,tree[x])\n",
    "                x+=x&(-x)\n",
    "            return \n",
    "        def query(x):\n",
    "            res=-inf\n",
    "            while x>0:\n",
    "                res=max(res,tree[x])\n",
    "                x-=x&(-x)\n",
    "            return res\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            b=bisect_left(temp,nums[i])\n",
    "            j=query(b)\n",
    "            ans=max(ans,j-i+1)\n",
    "            x=bisect_left(temp,nums[i])+1\n",
    "            update(x,i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        temp=sorted(list(set(nums+[-10000000000])))\n",
    "        ntemp=len(temp)\n",
    "        tree=[-inf]*(ntemp+1)\n",
    "        n=len(nums)\n",
    "        def update(x,value):\n",
    "            while x<=ntemp:\n",
    "                tree[x]=max(value,tree[x])\n",
    "                x+=x&(-x)\n",
    "            return \n",
    "        def query(x):\n",
    "            res=-inf\n",
    "            while x>0:\n",
    "                res=max(res,tree[x])\n",
    "                x-=x&(-x)\n",
    "            return res\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            b=bisect_left(temp,nums[i])\n",
    "            j=query(b)\n",
    "            ans=max(ans,j-i+1)\n",
    "            x=bisect_left(temp,nums[i])+1\n",
    "            update(x,i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        visd = [0] * len(nums)\n",
    "        num_w_idx = []\n",
    "        for i in range(len(nums)):\n",
    "            num_w_idx.append((nums[i],i))\n",
    "        num_w_idx.sort()\n",
    "        first = 0\n",
    "        ans = 0\n",
    "        for i in range(len(num_w_idx)):\n",
    "            num,idx = num_w_idx[i]\n",
    "            visd[idx]=1\n",
    "            if i+1<len(num_w_idx) and num==num_w_idx[i+1][0]:\n",
    "                continue\n",
    "            # visd[idx]=1\n",
    "            while first<len(num_w_idx) and visd[first]:\n",
    "                first+=1\n",
    "            if first==len(num_w_idx):\n",
    "                break\n",
    "            ans = max(ans,idx-first+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        num_w_idx = [i for i in range(len(nums))]\n",
    "        num_w_idx.sort(key=lambda x:(nums[x],x))\n",
    "        last = -1\n",
    "        ans = 0\n",
    "        print(num_w_idx)\n",
    "        lseen = -float('inf')\n",
    "        for i in num_w_idx:\n",
    "            if nums[i]==lseen:\n",
    "                last = max(i,last)\n",
    "                continue\n",
    "            ans = max(ans,last-i+1)\n",
    "            last = max(i,last)\n",
    "            lseen = nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        dc, res, mx = {}, 0, -1\n",
    "        for i, v in enumerate(nums):\n",
    "            if v in dc: dc[v][1] = i\n",
    "            else: dc[v] = [i,i]\n",
    "        for i in sorted(dc): res, mx = max(res, mx - dc[i][0] + 1), max(mx, dc[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        dc, res, mx = {}, 0, -1\n",
    "        for i, v in enumerate(nums):\n",
    "            if v in dc: dc[v][1] = i\n",
    "            else: dc[v] = [i,i]\n",
    "        for i in sorted(dc): res, mx = max(res, mx - dc[i][0] + 1), max(mx, dc[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "      dc, res, mx = {}, 0, -1\n",
    "      for i, v in enumerate(nums):\n",
    "          if v in dc: dc[v][1] = i\n",
    "          else: dc[v] = [i,i]\n",
    "      for i in sorted(dc): res, mx = max(res, mx - dc[i][0] + 1), max(mx, dc[i][1])\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, A: List[int]) -> int:\n",
    "        lo, hi = dict(), dict()\n",
    "        for i, x in enumerate(A):\n",
    "            if x not in lo:\n",
    "                lo[x] = i\n",
    "            hi[x] = i\n",
    "        \n",
    "        max_idx, res = -inf, -inf\n",
    "        for x in sorted(lo):\n",
    "            if res < max_idx - lo[x]:\n",
    "                res = max_idx - lo[x]\n",
    "            \n",
    "            if max_idx < hi[x]:\n",
    "                max_idx = hi[x]\n",
    "        return res + 1 if res > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        q=[]\n",
    "        for i,k in enumerate(nums):\n",
    "            q.append((k,i))\n",
    "        q.sort(key=lambda x:(-x[0],-x[1]))\n",
    "        res=0\n",
    "        mi=q[0][1]\n",
    "        lst=-1\n",
    "        for k,i in q:\n",
    "            if k!=lst and i>mi:\n",
    "                res=max(res,i-mi+1)\n",
    "            mi=min(mi,i)\n",
    "            lst=k\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            mp[num].append(i)\n",
    "\n",
    "        res = 0\n",
    "        maxRight = -inf\n",
    "        for key in sorted(mp):\n",
    "            pos = mp[key]\n",
    "            for p in pos:\n",
    "                res = max(res, maxRight - p + 1)\n",
    "\n",
    "            maxRight = max(maxRight, max(pos))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x].append(i)\n",
    "        result, right = 0, float('-inf')\n",
    "        for x in sorted(d):\n",
    "            result = max(result, *(right - i + 1 for i in d[x]))\n",
    "            right = max(right, *d[x])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            mp[num].append(i)\n",
    "\n",
    "        res = 0\n",
    "        maxRight = -INF\n",
    "        for key in sorted(mp):\n",
    "            pos = mp[key]\n",
    "            for p in pos:\n",
    "                res = max(res, maxRight - p + 1)\n",
    "            maxRight = max(maxRight, max(pos))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x].append(i)\n",
    "        ans, k = 0, inf\n",
    "        for x in sorted(d, reverse=True):\n",
    "            ans = max(ans, d[x][-1] - k + 1)\n",
    "            k = min(k, d[x][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        table = defaultdict(list)\n",
    "        for j in range(len(nums)):\n",
    "            table[nums[j]].append(j)\n",
    "        keys = sorted(table.keys())\n",
    "\n",
    "        ans = 0\n",
    "        rgt = -1\n",
    "        for ke in keys:\n",
    "            lst = table[ke]\n",
    "            for p in lst:\n",
    "                ans = max(ans,rgt-p+1)\n",
    "            rgt = max(rgt,max(lst))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            mp[num].append(i)\n",
    "\n",
    "        res = 0\n",
    "        maxRight = -inf\n",
    "        for key in sorted(mp):\n",
    "            pos = mp[key]\n",
    "            res = max(res, maxRight - min(pos) + 1)\n",
    "            maxRight = max(maxRight, max(pos))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            mp[num].append(i)\n",
    "\n",
    "        res = 0\n",
    "        maxRight = -inf\n",
    "        for key in sorted(mp):\n",
    "            pos = mp[key]\n",
    "            res = max(res, maxRight - min(pos) + 1)\n",
    "\n",
    "            maxRight = max(maxRight, max(pos))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        que = defaultdict(list)\n",
    "        for i, j in enumerate(nums):\n",
    "            que[j].append(i)\n",
    "        mx_idx = -1\n",
    "        for k in sorted(set(nums)):\n",
    "            tmp = que[k][0]\n",
    "            if mx_idx != -1 and tmp < mx_idx:\n",
    "                ans = max(ans, mx_idx - tmp + 1)\n",
    "            mx_idx = max(mx_idx, que[k][-1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def maxSubarrayLength(self, nums: List[int]) -> int:\n",
    "        lst = sorted([(x, i) for i, x in enumerate(nums)])\n",
    "        sl = SortedList([-1])\n",
    "        g = defaultdict(list)\n",
    "        for x, i in lst: g[x].append(i)\n",
    "        ans = 0\n",
    "        for k in sorted(g.keys()):\n",
    "            for i in g[k]: ans = max(ans, sl[-1]-i + 1)\n",
    "            for i in g[k]: sl.add(i)\n",
    "        return ans\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
